import Heap from '@/sources/Heap/maxHeap'
import { checkArr } from './util';



/**
 * 选择排序
 * 选出最大的元素，与最后一个元素交换
 * @param arr 
 */
export const selectionSort = (arr: number[]) => {
    if (checkArr(arr)) return arr;
    const len = arr.length;

    /**
     * 比较
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => arr[l] - arr[r]

    /**
     * 交换位置
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => {
        const tmp = arr[l]
        arr[l] = arr[r]
        arr[r] = tmp
    }

    // 遍历
    for (let i = 0; i < len; i++) {
        // 默认索引从0
        let max = 0

        // 从1开始循环
        for (let j = 1; j < len - i; j++) {
            if (compare(j, max) > 0) {
                max = j
            }
        }

        // 得到的最大值和最后的元素交换位置 (最后这里主要指的是还没排好序的情况)
        swap(max, len - i - 1)
    }
}

/**
 * 选择排序
 * 优化：使用二叉大顶堆来选择最大值
 * @param arr 
 */
export const selectionSort2 = (arr: number[]) => {
    if (checkArr(arr)) return arr;
    const len = arr.length;
    const heap = new Heap(arr)
    for (let i = 0; i < len; i++) {
        // 获取最大值
        const max = heap.remove();
        arr[len - i - 1] = max
    }

}
